import java.util.Arrays;


/**
 * @Author: LiuHeng
 * @Description:
 * @Date: 2022-09-13 0:04
 */
public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maximumSwap(2763));
    }

    /**
     * 611. 有效三角形的个数
     * 给定一个包含非负整数的数组 nums ，
     * 返回其中可以组成三角形三条边的三元组个数。
     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] != 0)
                for (int j = i + 1; j < n - 1; j++) {
                    int k = search_611(nums, nums[i] + nums[j]);
                    count += k - j - 1;
                }
        }
        return count;
    }

    //升序数组，第一个大于等于k的元素的下标
    private int search_611(int[] arr, int k) {
        int left = 0, right = arr.length - 1;
        int mid = 0;
        while (left<=right){
            mid = left + (right-left) / 2;
            if (arr[mid] < k){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 670.最大交换
     * 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
     */
    public int maximumSwap(int num) {
        int digit = 0;
        int num1 = num;
        int[] arr = new int[8];
        int[] help = new int[8];
        for (digit = 0; num > 0; digit++) {
            arr[digit] = num % 10;
            help[digit] = arr[digit];
            num /= 10;
        }
        Arrays.sort(help,0,digit);
//        for (int i = 0; i < (digit - 1) / 2; i++) {
////            int temp = help[i];
////            help[i] = help[digit-1-i];
////            help[digit-1-i] = temp;
//            swap(help, i, digit - 1 - i);
//        }
        int k;
        for (k = digit-1; k > 0; k--) {
            if (arr[k] != help[k])
                break;
        }

        if (k == 0)
            return num1;
        int j;
        for (j = 0; j < k; j++) {
            if (arr[j] == help[k])
                break;
        }
        swap(arr, k, j);

        num1 = 0;
        for (int i = digit-1; i >=0; i--) {
            num1 = num1*10 + arr[i];
        }
        return num1;
    }

    private void swap(int[] arr, int k, int j) {
        int temp = arr[k];
        arr[k] = arr[j];
        arr[j] = temp;
    }

    /**
     * 1608. 特殊数组的特征值
     * 给你一个非负整数数组 nums 。如果存在一个数 x ，
     * 使得 nums 中恰好有 x 个元素 大于或者等于 x ，
     * 那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
     */
    public int specialArray(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nums[n-1-i];
        }
        for (int k = 0; k < n; k++) {
            int index = search_1608(arr, k);
            if (index == k)
                return k;
        }
        return -1;
    }
    //降序数组，arr中第一个小于k的下标
    private int search_1608(int[] arr, int k) {
        int left = 0, right = arr.length - 1;
        int mid = 0;
        while (left<=right){
            mid = left + (right-left) / 2;
            if (arr[mid] >= k){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

}
